package com.lik.javadeep.stack;

import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * 中缀表达式的计算、并同时转为RPN
 */
public class Infix {
    private static String str = "0+1+4/4*5*7-8+9";
    private static Stack<Integer> valueStack = new Stack<>();
    private static Stack<Character> operatorStack = new Stack<>();
    private static Queue<String> rpn = new LinkedBlockingQueue<>();


    private static List<Character> characterList = Arrays.asList('(', ')', '+', '-', '*', '/', '^', '$');

    public static void main(String[] args) {
        // 头部放标识
        operatorStack.push('$');
        // 尾部放标识
        str += "$";

        // 遍历表达式
        for (int i = 0; i < str.length(); i++) {
            char current = str.charAt(i);

            // 如果是操作符
            if (isOperator(current)) {
                if (operatorStack.size() == 0) {
                    operatorStack.push(current);
                }
                // 先判断是否等到了执行时机
                String priority = getPriorityBetweenOperators(operatorStack.peek(), current);

                switch (priority) {
                    // 栈顶运算符，优先级更低。静待时机，操作符进栈
                    case "<":
                        operatorStack.push(current);
                        break;
                    // 栈顶运算符，优先级更高。时机已到
                    case ">":
                        while (">" == priority) {
                            char lastOperatorPop = operatorStack.pop();

                            appendRpn(lastOperatorPop + "");
                            // 这里只处理了 二元
                            if (valueStack.size() >= 2) {
                                int temp = doOperation(lastOperatorPop, valueStack.pop(), valueStack.pop());
                                valueStack.push(temp);
                            }

                            if (operatorStack.size() == 0) {
                                break;
                            }
                            priority = getPriorityBetweenOperators(operatorStack.peek(), current);
                        }

                        // 入栈
                        operatorStack.push(current);

                        break;
                    // 携手退出，直接出栈，不做额外处理
                    case "=":
                        valueStack.pop();
                        break;
                    default:
                        System.out.println("判断操作符号优先级出错");
                        break;
                }


            } else {
                // 是数字，直接读入后，入栈，这里只考虑一位数
                // 如果是多位数字，需要从栈中pop*10+current，然后push
                valueStack.push(Integer.parseInt(current + ""));

                appendRpn(current + "");
            }
        }


        for (Integer integer : valueStack) {
            System.out.println(integer);
        }

        System.out.println(getRpn());

        System.out.println("计算结果：" + evalRpn());
    }

    /**
     * @param
     * @return
     */
    private static boolean isOperator(char c) {
        return characterList.contains(c);
    }


    private static String getPriorityBetweenOperators(char lastOperator, char currentOperator) {
        int diff = getPriority(lastOperator) - getPriority(currentOperator);

        if (diff >= 0) {
            return ">";
        } else {
            return "<";
        }
    }

    private static void appendRpn(String s) {
        rpn.add(s);
    }

    private static String getRpn() {
        return String.join("", rpn);
    }

    private static int getPriority(char c) {
        if (c == '+' || c == '-') {
            return 1;
        }
        if (c == '*' || c == '/') {
            return 2;
        }

        if (c == '$') {
            return -1;
        }
        return -1;
    }

    private static int doOperation(char c, int num2, int num) {
        switch (c) {
            case '+':
                return num2 + num;
            case '-':
                return num - num2;
            case '*':
                return num2 * num;
            case '/':
                return num2 / num;
            default:
                System.out.println("doOperation出错");
                return 99;
        }

    }

    private static int evalRpn() {
        Stack<Integer> integerStack = new Stack<>();
        while (rpn.size() > 0) {

            String pop = rpn.poll();
            if ("$".equals(pop)) {
                continue;
            }

            // 是运算符就直接计算
            if (isOperator(pop.toCharArray()[0])) {
                Integer a = integerStack.pop();
                Integer b = integerStack.pop();
                int res = doOperation(pop.toCharArray()[0], a, b);

                integerStack.push(res);
            } else {
                // 如果不是运算符，则为数字
                integerStack.push(Integer.parseInt(pop));
            }

        }


        return integerStack.pop();
    }
}

